class Solution
{
public:
    long long maxTaxiEarnings(int n, vector<vector<int>> &rides)
    {
        map<int, long long> maxProfits; // maxProfits[k]表示到k处为止的最大盈利
        sort(rides.begin(), rides.end(), [](auto &r1, auto &r2)
             {
            if(r1[1] == r2[1])
            {
                return r1[0] < r2[0];
            }
            return r1[1] < r2[1]; });

        maxProfits[0] = 0LL;
        long long maxProfit = 0LL;
        for (auto &ride : rides)
        {
            auto beforeThisStart = --maxProfits.upper_bound(ride[0]);
            long long beforeThisStartProfit = beforeThisStart->second;
            long long thisMaxProfit = beforeThisStartProfit + ride[1] - ride[0] + ride[2];

            auto lastEnd = --maxProfits.upper_bound(ride[1]);
            long long lastEndProfit = lastEnd->second;
            thisMaxProfit = max(thisMaxProfit, lastEndProfit);

            maxProfits[ride[1]] = thisMaxProfit;
            maxProfit = max(maxProfit, thisMaxProfit);
        }
        return maxProfit;
    }
};